#include <iostream>
using namespace std;

const int N = 100010;

int e[N], ne[N],h,id;
int mp[N];

// 打印链表
void print()
{
    for(int i = ne[h];i;i = ne[i])
    {
        cout << e[i] <<" ";
    }
    cout <<endl  <<endl;
}

// 头插
void push_front(int x){
    id++;
    e[id] = x;
    mp[x] = id;
    ne[id] = ne[h];
    ne[h] = id;
}

// 按值查找
int find(int x){
    // 方法一：遍历链表
    // for(int i = ne[h];i;i = ne[i])
    // {
    //     if(e[i] == x)
    //     {
    //         return i;
    //     }
    // }

    // 方法二：用mp数组优化
    return mp[x];
}

// 任意位置插入
void insert(int p,int x){
    id++;
    e[id] = x;
    mp[x] = id;
    ne[id] = ne[p];
    ne[p] = id;
}

// 任意位置删除
void remove(int p){
    if(ne[p])
    {
        mp[e[ne[p]]] = 0;
        
        ne[p] = ne[ne[p]];
    }
    else
    {
        ne[p] = 0;
    }
}

int main()
{
    // 头插测试
    for(int i = 1;i <= 5;i++)
    {
        push_front(i);
        print();
    }

    // 按值查找测试
    // cout << find(3) << endl;
    // cout << find(5) << endl;
    // cout << find(10) << endl;

    //insert测试
    insert(1,10);
    print();
    insert(2,20);
    print();
    
    //remove测试
    remove(1);
    print();
    remove(2);
    print();

    


    
    return 0;
}
